package com.lw.leetcode.linked.b;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * 1673. 找出最具竞争力的子序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/22 15:34
 */
public class MostCompetitive {

    public static void main(String[] args) {
        MostCompetitive test = new MostCompetitive();

        // [2,3,3,4]
//        int[] arr = {2, 4, 3, 3, 5, 4, 9, 6};
//        int k = 4;

        // [2,6]
        int[] arr = {3, 5, 2, 6};
        int k = 2;

        int[] ints = test.mostCompetitive(arr, k);
        System.out.println(Arrays.toString(ints));
    }

    public int[] mostCompetitive(int[] nums, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int l = nums.length - k;
        for (int i = 0; i < l; i++) {
            int num = nums[i];
            while (!list.isEmpty() && list.peekLast() > num) {
                list.pollLast();
            }
            list.addLast(num);
        }
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            int num = nums[l++];
            while (!list.isEmpty() && list.peekLast() > num) {
                list.pollLast();
            }
            list.addLast(num);
            arr[i] = list.pollFirst();
        }
        return arr;
    }

}
